|
In theoretical computer science and formal language theory, a regular grammar is a formal grammar that is right-regular or left-regular. Every regular grammar describes a regular language. == Strictly regular grammars == A right regular grammar (also called right linear grammar) is a formal grammar (''N'', Σ, ''P'', ''S'') such that all the production rules in ''P'' are of one of the following forms: # ''B'' → ''a'' - where ''B'' is a non-terminal in ''N'' and ''a'' is a terminal in Σ # ''B'' → ''aC'' - where ''B'' and ''C'' are non-terminals in ''N'' and ''a'' is in Σ # ''B'' → ε - where ''B'' is in ''N'' and ε denotes the empty string, i.e. the string of length 0. In a left regular grammar (also called left linear grammar), all rules obey the forms # ''A'' → ''a'' - where ''A'' is a non-terminal in ''N'' and ''a'' is a terminal in Σ # ''A'' → ''Ba'' - where ''A'' and ''B'' are in ''N'' and ''a'' is in Σ # ''A'' → ε - where ''A'' is in ''N'' and ε is the empty string. A regular grammar is a left or right regular grammar. Some textbooks and articles disallow empty production rules, and assume that the empty string is not present in languages. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Regular grammar」の詳細全文を読む スポンサード リンク
|